package com.tgy.leetcode;

/**
 * @Author: tgy @Date: 2/4/21 9:09 AM
 *
 * 给出一个整数数组，有正有负。找到这样一个子数组，他的长度大于等于 k，且平均值最大。 保证数组的大小 >= k
 *
 * 例1:
 * 输入: [1,12,-5,-6,50,3] 3
 * 输出: 15.667
 * 解释: (-6 + 50 + 3) / 3 = 15.667
 *
 * 例2:
 * 输入: [5] 1
 * 输出: 5.000
 */
public class _643_子数组最大平均数_II_01 {


    public static double findMaxAverage(int[] nums, int k) {


        int len = nums.length;

        double min = nums[0];
        double max = min;


        for (int i = 1; i < len; i++) {

            if (nums[i] < min) {
                min = nums[i];
            }

            if (nums[i] > max) {

                max = nums[i];
            }
        }

        double mid;

        double[] sum = new double[len + 1];

        while (max - min >= 1e-6) {

            mid = (max - min) / 2 + min;
            double minPre = Double.MAX_VALUE;

            boolean flag = false;
            for (int i = 1; i <= len; i++) {

                sum[i] = sum[i - 1] + nums[i - 1] - mid;

                if (i > k) {

                    minPre = Math.min(minPre,sum[i - k]);
                    if (sum[i] > minPre) {
                        flag = true;
                        break;
                    }
                }
            }

            if (flag) {

                min = mid;
            }else {

                max = mid;
            }
        }

        return max;
    }


    public static void main(String[] args) {

        int[] nums = {1,12,-5,-6,50,3};
        int k = 4;
        double maxAverage = findMaxAverage(nums,k);
        System.out.println(maxAverage);
//        double maxAverage = maxAverage(nums, k);
//        System.out.println(maxAverage);
    }
}
